package huffmanTree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {

  public static void main(String[] args) {
    int[] array = {13, 7, 8, 3, 29, 6, 1};
    Node huffmanTree = createHuffmanTree(array);
    huffmanTree.preOrder();
  }

  public static Node createHuffmanTree(int[] array) {
    List<Node> nodes = new ArrayList<>();
    for (int value : array) {
      nodes.add(new Node(value));
    }
    Collections.sort(nodes);
    while (nodes.size()>1){
      Node leftNode = nodes.get(0);
      Node rightNode = nodes.get(1);
      Node parent=new Node(leftNode.value+rightNode.value);
      parent.left=leftNode;
      parent.right=rightNode;
      nodes.add(parent);
      nodes.remove(leftNode);
      nodes.remove(rightNode);
      Collections.sort(nodes);
    }
    return nodes.get(0);
  }
}

class Node implements Comparable<Node> {
  int value;
  Node left;
  Node right;

  public Node(int value) {
    this.value = value;
  }

  @Override
  public String toString() {
    return "Node{" + "value=" + value + '}';
  }

  @Override
  public int compareTo(Node o) {
    return this.value - o.value;
  }


  public void preOrder(){
    System.out.println(this);
    if (this.left!=null){
      this.left.preOrder();
    }
    if (this.right!=null){
      this.right.preOrder();
    }
  }
}
